Intro To Probability

3. Conditional Probability and independence

Example

(Gambler's Ruin)
Two gamblers, A and B, bet on the outcomes of successive flips of a coin. On each flip, if the coin comes up heads, A collects 1 unit from B, whereas if it comes up tails, A pays 1 unit to B. They continue to do this until one of them runs out of money. If its assumed that the successive flips of the coin are independent and each flip results in a head with probability p, what is the probability that A ends up with all the money if he starts with i units and B starts with $N - i$ units?

Let $E$ be the event A ends up with all the money starting with $i$ and $B$ starts with $N - i$ . Let H denote the event a flip lands heads. Then

P_{i} = P (E) = P (E | H) P (H) + P (E | H^{c}) P (H^{c})

= p P (E | H) + (1 - p) P (E | H^{c}) = p P_{i + 1} + q P_{i - 1}

where $q = 1 - p$ so we have

p P_{i} + q P_{i} = p P_{i + 1} + q P_{i - 1}

P_{i + 1} - P_{i} = \frac{q}{p} (P_{i} - P_{i - 1}) i = 1, 2, . . ., N - 1

since $P_{0} = 0$

P_{2} - P_{1} = \frac{q}{p} (P_{1} - P_{0}) = \frac{q}{p} P_{1}

P_{3} - P_{2} = \frac{q}{p} (P_{2} - P_{1}) = {(\frac{q}{p})}^{2} P_{1}

⋮

P_{i} - P_{i - 1} = \frac{q}{p} (P_{i - 1} - P_{i - 2}) = {(\frac{q}{p})}^{i - 1} P_{1}

⋮

P_{N} - P_{N - 1} = \frac{q}{p} (P_{N - 1} - P_{N - 2}) = {(\frac{q}{p})}^{N - 1} P_{1}

P_{i} - P_{1} = P_{1} [(\frac{q}{p}) + {(\frac{q}{p})}^{2} + \dots + {(\frac{q}{p})}^{i - 1}]

P_{i} = {\begin{cases} \frac{1 - (q / p)^{i}}{1 - (q / p)} P_{1} & if \frac{q}{p} \neq 1 \\ i P_{1} & if \frac{q}{p} = 1 \end{cases}

now using the fact that $P_{N} = 1$ we have

P_{1} = {\begin{cases} \frac{1 - (q / p)}{1 - (q / p)^{N}} & if p \neq \frac{1}{2} \\ \frac{i}{N} & if p = \frac{1}{2} \end{cases}

so finally

P_{i} = {\begin{cases} \frac{1 - (q / p)^{i}}{1 - (q / p)^{N}} & if p \neq \frac{1}{2} \\ \frac{i}{N} & if p = \frac{1}{2} \end{cases}

Remark

essentially when solving you should immediately recognize the need to solve for a recursive formula(just like you do for computational problems)